package mht.practice.heap;

import mht.practice.sort.SortTestHelper;

/**
 * Created by MHT on 2017/8/27.
 */
public class MinHeapSort {

    // 我们的算法类不允许产生任何实例
    private MinHeapSort(){}

    // 将所有的元素依次添加到最小堆中, 再在将所有元素从堆中依次取出来, 完成排序
    public static void sort(Comparable[] arr){

        int n = arr.length;
        MinHeap<Comparable> minHeap = new MinHeap<Comparable>(arr);

        //在创建堆的过程中就已经排好序了,现在只需要按顺序再放到arr数组中
        for( int i = 0 ; i < n ; i ++ )
            arr[i] = minHeap.extractMin();
    }

    // 测试 MinHeapSort
    public static void main(String[] args) {

        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        SortTestHelper.testSort("mht.practice.heap.MinHeapSort", arr);

        return;
    }
}
